HPAVC

home *** CD-ROM | disk | FTP | other *** search

/ HPAVC / HPAVC CD-ROM.iso / pc / CIS_GAME.ARJ / QMAPS1.THD < prev next >

Wrap

Text File | 1993-06-24 | 41.4 KB | 856 lines

______________________ Subj: Globe Surface Modelling ______________________ Fm: Eric J. Floehr 70003,442 # 186418 To: All Date: 10-Jul-92 14:46:58 Hello, The discussion about mapping a rectangular surface to a globe representation on the screen got me thinking that this forum might be a good place to ask a question I have. You all seem very knowledgeable and could probably answer this question! Basically, I have been working on a plate tectonic model (was inspired by a program for Xwindows by Dave Allen). The problem is, that unlike Allen's model, which uses a rectangular grid, I would like my model to work on a representation of the surface of a sphere. This rules out any rectangular array, because each square would not represent an equal area on the sphere. And, no "wrapping" rules could be easily constructed. I know I will need a custom structure, perhaps triangles, with functions to manipulate a surface or mesh of triangles (ie. each "square" only has 3 shared sides instead of four, which rules out using a standard 2d array). Anyway, I need to figure out exactly what "mesh" can be used to create an acurate representation within the computer of the surface of a sphere, with each "square" of equal area? Once I have that, I can use the mesh to create a standard projection to actually present the mesh on the screen. Any insights, pointers, or references? Thanks in advance, Eric ........................................................................... Fm: Mark Betz/GD SL 76605,2346 # 187183 To: Eric J. Floehr 70003,442 (X) Date: 12-Jul-92 20:47:15 Hi, Eric. I'm not the geometry ace around here, but it seems pretty clear from the outset that you won't be able to use rectangles. Some sort of triangular structure could be used, as in a geodesic dome. That would probably be the simplest structure in terms of vertices that need to be plotted. I guess we probably need to know more about what you're doing. You said a "plate tectonics model". I assume you're carving up the surface of the sphere into plates, and then modeling the forces between them. --Mark ........................................................................... Fm: Eric J. Floehr 70003,442 # 187382 To: Mark Betz/GD SL 76605,2346 (X) Date: 13-Jul-92 11:45:17 Mark, Thanks for the reply! I hadn't thought about the geodesic dome model, but I will definately look at how that is constructed to see if it will work as a structure for it. You are right, rectangles won't work, but make things a lot easier! Both in manipulation and display. I think that is one reason I am having so much trouble finding any articles or information on using something other than rectangles! I've looked for info on how the weather service, etc. do thier global models, but none of the books went into any detail. As for my model, it is going to be a plate tectonic simulator. It is not going to be rigorous in that it will use "realistic" modeling: ie. modelling the convection processes in the mantle, mostly because we know so little about it. But it will take into account most of the major known processes that change the earth: the creation of faults, rift valleys, mountains, etc. Since no one really knows, say, why a plate splits, etc. that will be fairly random but modelled in a "realistic" manner. For example, when a plate splits, the two plates will always rotate about a point on neither (usually) plate that can be intersected by the fault line. This behavior will then cause other plates to run into each other, or slide past each other. The ultimate purpose of this project is not only for obvious educational purposes, but for those that may wish to "create worlds" with a more realistic flavor and more "history" than a fractal-based creation. The next step in the process would be climactic determinations (ie. when, where, and why an area of land would be a desert, etc.) But that is a ways off! Again, thanks for your help! -Eric ........................................................................... Fm: Eric J. Floehr 70003,442 # 188201 To: Mark Betz/GD SL 76605,2346 (X) Date: 15-Jul-92 22:35:33 Mark, I've had a chance to think about the problem of creating a globe structure in the computer and I've come up with a solution. I thought about overlaying triangles and other regular shapes unto a sphere, and thought about the idea of geodesics. However, the problem with that is that they aren't squares (and as you and I know, square representation is much simpler!), and that the pattern itself would be irregular (ie. you would have to include pointer information, unlike using a rectangular array where its position determines its neighbors). Then of course, one would need an identifier to each triangle. Needless to say it wouldn't be an elegant solution. But while I was thinking about how one would map a point to a particular area (like a triangle), I thought about how we do it on our globe: latitude and longitude. Obviously, the problem with lat and long is that while each lat division occurs at an equal spacing, the longitudes spread out from the pole to the equator. So think of this: squares can be used to ensircle an area around the equator, and around the meridian. If we want to be neat, we could choose the number of squares such that a square sits over both poles. Thus, we choose 4, 8, 16, 32, etc. squares to do this. The squares would not be distorted, and each square would have an equal area. Now, the line through the centers of each square on the equator forms the 0 latitude. The line through the first square above the equator on the meridian forms latitude 1, etc. We could then string these squares along each latitude, squeezing or streching each latitude to create an integer number of squares (which would only incorporate minor and acceptable distortion). Formally, the number of squares for a given latitude can be found by: (# squares around eq. & meridian) * cos((360 / # squares) * lat. line) For example, if we place 16 squares around the meridian and equator: N. Pole: 1 square Lat. 3 : 6 Lat. 2 : 11 Lat. 1 : 15 Equator: 16 Lat. -1: 15 Lat. -2: 11 Lat. -3: 6 S. Pole: 1 Then, the only mapping (and it can be a mathmatical rather than physical mapping) is from one lat. to another. From long. to long. there is only a standard array. Obviously there is some error, since we will end up with "gaps" where there is a non integer number of squares needed to fill at lat.. These gaps however, average out. Look at the chart for the remarkable closeness of fit of this model: Circum is the number of squares around the equator and meridian, EF is my method, and Real is the actual surface area for a sphere of given circumfrence, and then the error. Circum: 32 EF: 328 Real: 325.949 Error: 0.6291397% Circum: 64 EF: 1302 Real: 1303.797 Error: 0.1378507% Circum: 128 EF: 5218 Real: 5215.189 Error: 0.0538969% Circum: 256 EF: 20860 Real: 20860.757 Error: 0.0036274% Circum: 512 EF: 83442 Real: 83443.027 Error: 0.0012305% Circum: 1024 EF: 333772 Real: 333772.107 Error: 0.0000321% Circum: 2048 EF: 1335088 Real: 1335088.429 Error: 0.0000321% Circum: 4096 EF: 5340340 Real: 5340353.715 Error: 0.0002568% Circum: 8192 EF: 21361402 Real: 21361414.862 Error: 0.0000602% Circum: 16384 EF: 85445714 Real: 85445659.447 Error: 0.0000638% Circum: 32768 EF: 341782596 Real: 341782637.787 Error: 0.0000122% Circum: 65536 EF: 1367130648 Real: 1367130551.148 Error: 0.0000071% Obviously, a 1024 circumfrence is the last practical one (326K is quite large for an array!), and the error is 3/100,000 of a percent. See any flaws? I haven't but I could be wrong. Let me know what you think! Thanks, -Eric ........................................................................... Fm: Mark Betz/GD SL 76605,2346 # 188425 To: Eric J. Floehr 70003,442 Date: 16-Jul-92 17:26:59 Hi, Eric. I have to be careful here, because I'm more than a bit out of my league. However, my impression is that you aren't modeling a sphere, but rather a "wedding cake" arrangement of circular solids. Imagine taking a cross section of your world bisecting the north and south poles... __ __|__|__ __|__|__|__|__ |__|__|__|__|__| |__|__|__| |__| As you point out, the result is sort of analogous to aliasing in a digitized image: you lose some information. How much depends on the size of your squares. If the resulting resolution is enough for your purposes, then you're ok. Another possibility is representing the surface of the globe as a spherical array of contiguous points in three-space. Given one point, the diameter of the sphere, and probably some other esoterics of which I'm ignorant, you could calculate the position of the next point in any direction. --Mark ........................................................................... Fm: Eric J. Floehr 70003,442 # 188550 To: Mark Betz/GD SL 76605,2346 (X) Date: 16-Jul-92 23:32:50 Mark, Whoops! It seems I didn't really make myself clear, and I appologize. Actually the idea is not one of cubes, but one of squares. Remember that I am trying to model the surface of the sphere, and have no interest in either its exterior or interior. Let me explain my model by using a little more practical example, and hopefully I can articulate this a little better: Say you have a sphere, that you want to glue squares onto (for whatever reason) So you cut out squares of the same size, get your glue out, and go to work. The easiest and most logical place to start would be the equator. Lets say we manage it so that it takes exactly 16 squares to go completely around equator. There will be some slight overlap since a flat square needs to fit on a curving surface, but it is minimal and can be ignored. We do the same with the meridian, so we have two "equators", one horizontal and one vertical, intersecting exactly at two places. Then, since latitude lines always have equal spacing but longitude lines don't (they are the widest at the equator and converge to a single point at the poles), we need to start covering the globe in latitudinal "strips". So start gluing squares from the square directly above the equator on the meridian. As you glue around the sphere, you will find that after you place your 14th square, there will be room for about 78% of a 15th square, so you squish the squares so you can fit 15 squares in. Then, for the square on the meridian above both those lines, you'll end up with 30% of a square gap after the 11th square, so you'd need to stretch them a little. Then, for the next, you'll end up placing 6 squares, with about a 12% of a square gap. Then you'll have the poles. Pulling the glued squares from the sphere you'd end up with "strips of squares" like: __ |__|__ __ __ __ __ |__|__|__|__|__|__|__ __ __ __ __ |__|__|__|__|__|__|__|__|__|__|__|__ __ __ __ |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__ |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__| |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__| |__|__|__|__|__|__|__|__|__|__|__| |__|__|__|__|__|__| |__| Obviously, there will be a lot of overlap of the squares on the curves surface, but this decreases as each square becomes less of a percentage of the surface area. Is this clearer? Let me know if it isn't. As for projection: a Mercator projection becomes simple: just take the graphic above, and stretch each strip horizontally, stretching each square equally, until they all match up. Something like: _______________________________________________ |_______ _______ _______ _______ _______ _______| |___ ___|____ __|____ __|_ ___ _|_ ____ |__ ____| |___|___|____|___|___|____|___|___|____|___|____| |___|__|__|__|__|___|__|__|__|__|___|__|__|__|__| |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__| |___|__|__|__|__|___|__|__|__|__|___|__|__|__|__| |___|___|____|___|___|____|___|___|____|___|____| |_______|_______|_______|_______|_______|_______| |_______________________________________________| And, in fact this is how the "mapping" works in going from one latitude to another: 16 squares at the equator mapped to 15 at latitude 1, 15 mapped to 11, etc. Then, of course, in the computer each strip is modelled as a 1D array of say integers, so each square can then contain an altitude, or some other info. -Eric ........................................................................... Fm: Mark Betz/GD SL 76605,2346 # 188579 To: Eric J. Floehr 70003,442 (X) Date: 17-Jul-92 00:26:54 Hi, Eric. That was a better explanation ( the drawings don't hurt <g> ), but I think I basically had it the first time. It still looks to me like there's a problem with the model. Since you've tried to make your concept clearer, I'll try to do the same for my objection. You've compensated for the varying diameter of a sphere at different latitudes using varying numbers of squares. Indeed, you end up with the right value for the circumference of the sphere at _some_ point along the y-axis of each square. But the problem is that squares won't map to a sphere. They have to be trapezoids. If you take a set of your squares as a strip wrapped around the sphere at a given latitude it's clearer: the circumference of the strip is the same at min and max y, making it a cylinder, not a section of a sphere. This is what I was trying to illustrate with the drawing in my reply. To me this seems analogous to the aliasing that takes place when a smooth curve is rendered into a specific display resolution. Since you can't represent the smooth, curved surface of a sphere using squares, what you end up with is a chunky model of a sphere constructed of cylindrical solids stacked one on top of another. The resolution of the model will depend on the number and size of the squares. --Mark ........................................................................... Fm: Eric J. Floehr 70003,442 # 188710 To: Mark Betz/GD SL 76605,2346 (X) Date: 17-Jul-92 12:44:01 Mark, Those ASCII drawings sure are tough to make though! <G> OK, I understand your point about the overlap, and you are right. For example, using our 16 square circumfrence model, the circumfrence through the middle of the squares on the meridian directly above the equator is 14.78 to which we fit 15 squares. However, the circumfrence at the bottom edge of the squares is 15.69 and at the top it is 13.30 squares. In other words we would need to stretch out the bottoms and squish the tops, creating a trapezoidal structure, rather than a square. This becomes worse at the pole where the median is 6.12, but the bottoms are 8.89 and the tops are 3.12 squares. Do I understand your argument correctly? I take your point, and perhaps I was a little sloppy in my use of geometric figures :) Saying I use squares and stretch them and squeeze them to fit is that same as saying I use trapezoids and stretch and squeeze them a little less. Physically this matters, but conceptually it doesn't. An string of objects around the latitude can be squares or trapezoids, or better yet a trapezoid that resides in sphere-space rather than in Euclidean flat-space, the only thing that matters is that the model must exactly model the sphere when the number of objects goes to infinity, and that at coarse resolutions, the objects' areas sufficiently approximate the sphere's surface. So long as our squares in our model have an area of 1, it doesn't matter how it gets that area, and you are right in saying that it would better get that area (and in fact can only get that area) if the objects are modelled more closely to trapezoids than to squares. I think we were both dancing around the same point on this issue! As far as your second issue, I think I understand better what you are getting at, but I dunno. But let me make this comment. We need to make the distiction between Euclidean flat geometry and sphere (what is the name, Lympanov?) geometry because they are different and irreconcilable. That is why we can never convert exactly between the 2D space of the surface of a sphere and the 2D space of a flat plane. My model must reside in sphere-space, not in flat-space, and therefore the only aliasing done is the same that is done when converting a space with infinate points into a finite representation. And you can never ever get around that. Thanks for your input and suggestions, they have really helped me. I hope we can continue this conversation. -Eric ........................................................................... Fm: Mark Betz/GD SL 76605,2346 # 188779 To: Eric J. Floehr 70003,442 (X) Date: 17-Jul-92 17:40:37 Yep, that's basically what I'm saying. The second "issue" wasn't really an issue, but rather an attempt at an analogous explanation. If you use squares to fit the surface of a sphere, you will only be able to approximate the true shape of it. Similarly a curve cannot be perfectly rendered in pixels. In this case the pixels are analogous to your squares. The larger the pixels, the less true the curve; the larger the squares, the less your model will resemble the true surface of a sphere (which was, after all, Euclid's "most perfect solid" <g>). Using trapezoids will yield the same effect, but you will be able to construct a truer model. --Mark ........................................................................... Fm: Eric J. Floehr 70003,442 # 188799 To: Mark Betz/GD SL 76605,2346 (X) Date: 17-Jul-92 18:22:53 Mark, Its great that we have finally come to terms! <G> I intend to dabble with some implementations this weekend and see what I can come up with. Once I have the "globe engine", it will be easy to use it for many applications, as opposed to integrating it with the tectonic simulator, where it can't be used again. Of course, then the next part is actually creating the simulation, which is a different story! (I wonder how I could relate the tectonic sim to a game to make it more appropriate for this section? Escape the Earthquake, Venture to the Volcano, Find the Fault? :) ). -Eric ........................................................................... Fm: Jesse Montrose 76646,3302 # 188705 To: Eric J. Floehr 70003,442 (X) Date: 17-Jul-92 12:10:43 Eric, > We could then string these squares along each latitude, squeezing or streching each latitude to create an integer number of squares (which would only incorporate minor and acceptable distortion). Don't forget that your "squares" are not at all square once you get off the equator and meridian. The closer you get to a pole, the greater the difference between the bottom & top widths of the shape. I call it a shape, because it won't even be a trapezoid, the sides are curved. I don't think you should give up on the geodesic model. You could still use relatively simple arrays, instead of pointers: (just imagine these are real triangles [g]) equator vector: /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ vector 1 : \/\/\/\/\/\/\/\/\/\/\/\/\/\/ (a little shorter) vector 2 : /\/\/\/\/\/\/\/\/\/\/\/ (etc..) . . . pole vector : \/\/\ For any given triangle, two of it's neighbors will be next to it on the vector, and the third is just a simple percentage calculation into the adjacent vector. If it's too jagged, you can just add more triangles, until you can't see the jags anymore... [g] ........................................................................... Fm: Eric J. Floehr 70003,442 # 188712 To: Jesse Montrose 76646,3302 Date: 17-Jul-92 12:52:16 Jesse, See my latest response to Mark on that. Basically you are right, but it doesn't matter what the actual shape is (within reason) so long as its area in sphere-space is 1. Thanks for your comments, and I hope to talk with you soon. -Eric ______________________________ Subj: Hex Maps ______________________________ Fm: William D. Vaughn 74720,1246 # 308941 To: all Date: 05-Mar-93 22:12:41 Can anyone give me some tips on representing (in C or C++) a hex (hexagon) map sheet? I would need to determine the range between two hexes and determine which hexes fall between two hexes (line of sight). One thing that has occured to me is to just use two-d array: hextype map [NROWS][NCOLS]; And then have the routines take into account that every other row is indented. To see this, imagine a chess board where every other row is indented half a square. Each square now touches 6 other squares and you have something similar to a hex map. I think I would have serious problems getting this to work correctly, particularly line of sight. Another idea: something kind of similar to a linked list: struct hextype { int terrain, elevation; hextype *NW, *NE, *E, *SE, *SW, *W; }; This is a little more elegant, but how do you determine range? If one hex could tell which of its surrounding hexes is closest to the target, you could have some sort of recursive function that traces the path between the two, thus revealing range and line of sight. But, how do you determine which of the surrounding hexes is closest to the distant target? What makes this method diffcult seems to be that the hexes are so isolated, only having contact with adjacent hexes. And, they have no positioning information, other than relative to the surrounding hexes. How about something that makes use of the numbers printed on each hex on an actual map sheet to determine some position information? If I want to get really abstract, Robert Sedgewick's "Algorithms in C++" has a section on geometric algorithms, which deal with graphs (sets of vertices) and determine the shortest route between them, etc. Even if I could get something like this to work, seems like it would be overkill for a simple hex map. Any suggestions out there? This is my first post to CIS, so if I've done something uncool please let me know. Dominic Vaughn 74720,1246 vcsc2059@sfsuvax1.sfsu.edu ........................................................................... Fm: Bob Provencher/GD SL 71621,2632 # 309235 To: William D. Vaughn 74720,1246 (X) Date: 06-Mar-93 13:51:52 Hi William, Welcome to GAMERS! I've thought about this a little bit, and one idea I've come up with is a 2d array, with a 1/2 square shift on every other line. On the even lines, add 1/2 to the array co-ordinate to find the "real" center of the hex, which can then be used for distance calculations. I think this will also work for line of sight, if you've got two hexes, then step through all the hexes in the enclosing rectangle, shifting when appropriate, and decide how far from the line-of-sight each hex is, by taking the perpendicular to the line and the hex in question and computing the distance. If it's within the .5 "squares" then it's in the line of sight. Hope this helps. Bob ........................................................................... Fm: William D. Vaughn 74720,1246 # 309447 To: Bob Provencher/GD SL 71621,2632 (X) Date: 06-Mar-93 20:49:32 Thanks for the advice Bob. I was leaning towards the 2-d array idea myself, but it seemed rather difficult because I was thinking of geometric objects instead of points. It does seem pretty easy now: each hex's x and y coordinate are determined by their array index, with every even row adding 0.5 to one of the coordinates. Range determined by feeding two points into the distance formula. And LOS determined by distance between a hex's coordinates and the line connecting the the other two hexes. Hopefully it will still seem that simple when I start writing code. Thanks again for the help. Dominic Vaughn ........................................................................... Fm: yngvi 76703,3046 # 309244 To: William D. Vaughn 74720,1246 (X) Date: 06-Mar-93 14:06:06 Your first idea is a good one -- consider the hex map as a brick wall -- alternating rows of overlapped squares or rectangles. Your graphics can then display the map as hexagons. LOS and other direction calculation in hex maps is actually pretty simple if you use 'slant matrix' calcs. Unfortunately I dont have the calcs here. They're pretty basic, but I wouldnt want to guess. The idea is that you transform the coordinates in a way that lets you number along diagonals rather than rows & columns. once you do that the distance calcs are easier. LOS is more difficult since you have to check multiple directions, but not overwhelming. There were a coupla articles on this in BYTE a long time ago (early 80's), and I'll try to dig them up. btw, the LOS calcs in my online sniper game are probably the most complicated part of the program -- running about 30 pages of code. One big problem is that calculations are not always reciprocal -- since you're dealing in discrete units (squares or hexes), diagonal lines are not always duplicated due to rounding. So a tree may block when calculated in one direction but not in the other. This leads to cases where one player has LOS and the other doesnt (not appreciated by the second player). My eventual solution was to always do both calculations and allow the shot if either player has LOS. this sometimes leads to odd looking shots, but it makes the game more fair. ........................................................................... Fm: William D. Vaughn 74720,1246 # 309448 To: yngvi 76703,3046 (X) Date: 06-Mar-93 20:49:38 30 pages of LOS code? Ouch! I get the feeling mine will be a lot shorter because my needs are simpler. For one thing, with the way I have decided to go (2-d array) it will be very difficult to get LOS to exactly match what I get with a hex map. I am trying to write something for BattleTech. In that game, if the line connecting the centerpoints of two hexes crosses over even the tiniest portion of another hex, that hex is in the LOS. With the method I am going to try (suggested by Bob), a hex is in the LOS if it's centerpoint is within 0.5 units (half a square) of the line connecting the other two hexes. What you end up with is the equivalent of circular hexes, which is close enough for my needs (I don't need to get the exact same results as the board game). Thanks for your advice. That alternate geometry you mentioned sounded intertesting. I guess that would be something oriented towards 60 degree angles instead of 90 degrees. Dominic Vaughn ........................................................................... Fm: yngvi 76703,3046 # 309772 To: William D. Vaughn 74720,1246 Date: 07-Mar-93 12:56:27 One reason I couldnt use direct lines is speed -- calculating line connecting 2 points requires too much cpu. So I use a method that's similar to that for drawing diagonal lines of pixels -- moving one pixel/square at a time, and incrementing when needed. That's where the discrepancy comes in -- eg, if the 2 pts are corners of a 13x3 box, you'd increment every 5: Xxxxx........ xxxxx xxY Starting from the other side, you'd see: ........xxxxY xxxxx Xxx.. So the same squares aren't always checked. Another problem comes up with special cases like stone walls: ###X############### .............Y Here X is in a window (# = bldg walls). If you use the normal algorithm for either of these guys, it would hit a wall at some point and they would be unable to sight. So there need to be special routines to handle these sorts of situations. ........................................................................... Fm: Dave Menconi 72350,602 # 310815 To: William D. Vaughn 74720,1246 (X) Date: 09-Mar-93 01:28:34 My approach to LOS and ranges would be to mimic the calculation you would do in a board game. I would develop an algorithm that would actual "walk" the grid from one point to another. For range you count the hexes; for LOS you look for blocking hexes. For range this would be slower than a mathematical solution. For LOS I can't see how you can avoid walking the hexes. Since you have to walk the hexes using a graph would be a pretty good solution (it seems counter-intuitive -- seems like some kind of array would be better). You can use a breadth-first search to find the shortest route(s) and then check to see if any of the hexes are blocked. Remember that in most games there is some limit to how far you go -- the weapons have ranges and past those ranges it might as well be infinite. This means that you can trim the searches. Also, a bredth first search on a 6-way graph could be pretty costly but you can reduce it if you limit the search to look only in a particular direction. Dave ........................................................................... Fm: William D. Vaughn 74720,1246 # 311370 To: Dave Menconi 72350,602 (X) Date: 09-Mar-93 23:53:49 Dave, I agree with you that having the program walk the hexes is the best way to determine range and LOS. I had replied to someone else on this thread that I was going to try to do everything with simple math: use the distance formula to calculate range, to determine if a hex blocks LOS calculate it's distance from line, etc. Once I started writing the code, I realized that it was just too unfaithful to the game mechanics of an actual hex map. In my orignal post I mentioned the possibility of using using graphs and breadth-first searches. I am now leaning against this. For one thing, it just seems inefficient. The graph routines are designed for random points and vertices, and I don't know if there is any way to let them take advantage of the regularity and structure of a hex map. The other reason: I've looked at the code for graphs, and do have a dim understanding of them, but I don't know if I could write them. My current plan is to use a 2-d array of hexes. Each hex would contain, among other things, an X and Y coordinate. To walk the map between hexes A and B, I would: 1. Calculate angle between A and B (using their x and y coordinates) 2. Determine which of the 6 hexes surrounding A is closest to that angle. (for example, the angle to the NW hex is 120 degrees, so if the angle between A and B is closer to 120 than to 60 or 180, the NW hex would be chosen) 3. Call that hex C. If C=B, we are done. Otherwise, go to step 1 using C and B. William ........................................................................... Fm: yngvi 76703,3046 # 311583 To: William D. Vaughn 74720,1246 (X) Date: 10-Mar-93 13:43:29 There will still be times when you travers hex edge, rather than move thru the hex itself. Whenever you traverse a hexside the terrain on both sides is relevant. The rules may vary -- it may be that blocking terrain in either hex will block LOS, or blocking terrain must be in both hexes to block. So for every hexside, you will need to start a new thread to follow. In addition, your calculation of 'best' angle is still going to depend on which hex you use as your starting point. Rounding will still be a factor -- eg, the choice of hex used for A to B might not be the same as that for B to A. This is analogous to drawing a line pixel by pixel. Since you're mapping a continuous line to a discrete coordinate system, the result will not be a smooth line. ........................................................................... Fm: Dave Menconi 72350,602 # 310828 To: Bob Provencher/GD SL 71621,2632 (X) Date: 09-Mar-93 02:36:42 Notwistanding what I said before, I don't think a graph is the way to go. I reached that conclusion by considering the best way to create a graph. First you put all the data into an array. Then you make each link a 2 byte index into the array. That way you save 12 of the 24 bytes. But you might as well make the array 2 dimentional and make the 2 byte indexes 2 1 byte indexes. Well, you quickly see that you can calculate the 6 indexes that I was going to store so you don't need to store them. There you are with your 2 dimentional array... The way Chris Crawford calculated LOS and range in Tanktics (I didn't write it but I certainly saw the code) was to calculate a primary and secondary direction that the target hex has from the starting hex. Then he would look in each of the two hexes and consider which one had the "best" terrain for the particular purpose (usually you're trying to figure out more than the shortest distance -- cover and movement points were also considered). Then he would step in that direction, find a new primary and secondary hex and do it again. If you just want the shortest (in number of hexes) distance you can always use the "primary" direction and just keep stepping in that direction. You can get "fewest movement points" using the primary/secondary technique. Note that a breadth first search will give you a better answer than the primary / secondary method in some cases but not THAT much better. I'm sorry but I can't remember what the algorithm for figuring out the primary and secondary hexes are... ........................................................................... Fm: Bob Provencher/GD SL 71621,2632 # 311107 To: Dave Menconi 72350,602 (X) Date: 09-Mar-93 16:50:43 Hi Dave - I can't think of any benefits to the graph method. One idea I had was the ability to find the shortest non-obstructed path between two hexes, using matrix representations of each hex, and something called Warshalls algorithm. The problem is that the algorithm is O(n^3)! For line of sight I can't see how the graph would work either. I guess I need to understand the algorithm your talking about. It sounds like it is the same for both the LOS and shortest path calculation, which to me are very different. Bob ........................................................................... Fm: Dave Menconi 72350,602 # 311399 To: Bob Provencher/GD SL 71621,2632 (X) Date: 10-Mar-93 01:07:58 Bob, As I say, it is possible to calculate the range without stepping in each hex; you can do it mathematically. I don't know the algorithm off hand but I know that others have found it so it must exist (they think therefor it is? -- no never mind <G>). On the other hand, you must step in each hex to get the LOS -- it can't be done mathematically. So you have to write a "walk the line" routine. Since you have write one anyway, and since it WILL give you the range (if you write it so that it will) why not use it to give you the range? It won't be as efficient but it will be plenty fast enough (it was plenty fast enough on an Atari 800 and on a Kim -- it will be fast enough on a PC or a Mac!). The algorithm is so simple it's almost stupid. It's O(n) where n is the range. The only thing you need (that I don't know how to do) is a routine that will tell you which of the 6 directions to go in to get from one hex to another. I think you compare the x and y (actually the delta x and delta y) but I'm not sure what the exact algorithm is. Dave ........................................................................... Fm: yngvi 76703,3046 # 311584 To: Dave Menconi 72350,602 (X) Date: 10-Mar-93 13:43:34 Right, the slant matrix algorithm will give distances by simple addition and subtraction, so is quite fast. Calculating the range is handy to do first, since you can eliminate LOS calcs for anything out of range. You can also find the closest (or strongest, whatever) target in range first, and then do detailed LOS calcs. Steve ........................................................................... Fm: Bob Provencher/GD SL 71621,2632 # 311666 To: Dave Menconi 72350,602 (X) Date: 10-Mar-93 17:40:36 Hi Dave - I'm curious, have you implemented the LOS by walking stepping hexes? I'd like to see it because I'm really confused as to how to do it that way. Or do you mean you "walk the line" and step through the intersecting hexes? (That's the way I suggested it be done at the beginning of the thread) Bob ........................................................................... Fm: Dave Menconi 72350,602 # 311974 To: yngvi 76703,3046 Date: 11-Mar-93 01:10:19 Steve, It may solve the first problem (hex edge traversal) to have the routine return 2 hexes -- a primary and a secondary. Perhaps it could also return a value that indicates how secondary the secondary hex is (i.e. how close to the hex edge is the line). In cases where the secondary hex is considered important, one could add a rule that the LOS is blocked only if the primary and secondary hexes are BOTH blocked. I would not actually move into the secondary hex and check line of sight recursively from there because that seems to be a) very expensive in time and space and b) of marginal value (i.e. only rarely would you get different results). Waddaya think? Would this shortcut yield reasonable results? Now, about your second point (AB isn't the same as BA). Perhaps you could always draw the line in the same direction. For example, you might always pick the hex that's farthest up and to the right to start from. That means that AB still isn't the same as BA but we always calculate AB, never BA so we always get the same answer. Cheap and dirty but workable, right? Dave ........................................................................... Fm: Dave Menconi 72350,602 # 311973 To: William D. Vaughn 74720,1246 (X) Date: 11-Mar-93 01:10:11 William, I'm wondering how you will calculate that angle. Will the standard angle calculation (arctangent of dy/dx) work in a hex grid!? Also, since you only need 6 possible angles, it should be possible to simplify the algorithm. Dave ........................................................................... Fm: William D. Vaughn 74720,1246 # 312481 To: Dave Menconi 72350,602 (X) Date: 12-Mar-93 01:05:32 Dave, yes I used atan (dy/dx), though there were a couple of minor hassles. For one thing, I had to make adjustments to this if the point did not lie in quadrant I (eg., for dy and dx both negative I used atan(dy/dx)+PI). Also dx=0 required special treatment. I converted the result to degrees. As for where I got the coordinates: I used the hex's array index. For example, the first hex in each row has x=0, the fourth has x=3, etc. The y coordinate was a little trickier. If the distance between hex centers is 1.0 horizontally, it is sqrt(.75) vertically. I made this a constant (const double VERTFACT=sqrt(0.75) ) and set each hex's y coordinate to rowNum * VERTFACT. Also, every odd numbered row is indented by 0.5, or x=x+0.5. Taking all into account, hex [11][3] has coordinates (11.5, 2.598). This is about as far as I've gotten. The next step will be to determine which of the six directions is closest to the angle between two hexes, which will simply require rounding the angle to the nearest 60 degrees. Then it shouldn't too hard to walk the range! (I hope anyway). William ........................................................................... Fm: Dave Menconi 72350,602 # 311971 To: Bob Provencher/GD SL 71621,2632 (X) Date: 11-Mar-93 01:10:02 Bob, I'm talking about "walking the line." I'm sorry, I must have missed your description. I think I confused you by talking about the Tanktics movement algorithm. It would not just travel the straight line between two points but actually try to find "the best path" according to a set of rules. It was kind of cute because it would travel through clear terrain at the beginning of the turn and then "duck into" good cover at the end of the turn so that units were always in cover when the other player got to shoot. <G> Dave ........................................................................... Fm: Bob Provencher/GD SL 71621,2632 # 312225 To: Dave Menconi 72350,602 (X) Date: 11-Mar-93 16:47:24 Hi Dave - Oh ok, I see! Yeah, ducking into cover is a healthy thing for a unit to do before the opponents turn <g>. Bob ...........................................................................